1. Technical Field
The present invention relates to whole-body computer aided detection/diagnosis (CAD) scheduling.
2. Discussion of the Related Art
Recently, emerging whole-body imaging technology has paved the way to scale up medical image-based diagnosis to a whole-body level. Whole-body computed tomography (CT)/positron emission tomography (PET)/magnetic resonance (MR) scanning help radiologists in various diagnostic problems, including assessment of cancer metastasis in lymph (D. Visvikis and P. J. Ell, “Impact of technology on the utilisation of positron emission tomography in lymphoma: current and future perspectives”, European Journal of Nuclear Medicine and Molecular Imaging 30, pp. 1619-1670, 2002) or bones (M. Niitsu and T. Takeda, “Solitary hot spots in the ribs on bone scan: value of thin-section reformatted computed tomography to exclude radiography-negative fractures”, J Compu Assis Tomogr. 27, pp. 469-474, 2003), evaluation of the extent and distribution of polymyositis (M. O'Connell, T. Powell, D. Brennan, T. Lynch, C. McCarthy and S. Eustace, “Whole-body mr imaging in the diagnosis of polymyositis”, AJR Am J Roentgenol. 179, pp. 967-971, 2002), and detection of ankylosing spondylitis (U. Weber, C. W. Pfirrmann, R. O. Kissling and J. H. M. Zanetti, “Whole body mr imaging in ankylosing spondylitis: a descriptive pilot study in patients with suspected early and active confirmed ankylosing spondylitis”, BMC musculoskeletal disorders 8, 2007). However, the vast amount of image data in whole-body scans (more than 400 slices) makes the detection of potential disease a burdensome and tedious task for radiologists. Accordingly, CAD becomes more desirable for whole-body scans to provide a useful “second opinion” for radiologists.
As a whole-body CAD system often involves multiple organs that have strong anatomical or functional dependency, it is actually a multi-task system where different tasks are highly dependent. One way to exploit task dependency is to execute the tasks in a schedule such that outputs of some tasks can be used to guide the others. For example, the relatively easy task of femoral head localization in CT (bone is very bright in CT) will facilitate a quick and accurate localization of the iliac bifurcation of the aorta, which in turn greatly helps the detection and identification of abdominal lymph node clusters (see FIG. 1). However, while the idea of executing multiple tasks of whole-body CAD in a particular order has been accepted, whole-body CAD is usually scheduled heuristically and the scheduling method (how to determine the schedule?) has not been well investigated.
In the past decades, scheduling topics have been extensively studied in the areas of operation research (P. Brucker, “Scheduling algorithms”, 4th edition, Springer, 2004) and theoretical computer science (K. Pruhs, J. Sgall and E. Torng, Handbook of Scheduling: Algorithms, Models, and Performance Analysis, CRC Press, 2003). Many scheduling rules/methods were proposed to deal with scheduling problems in various applications, including manufacturing, service industries, transportation and practical computer systems, etc. While earlier studies (J. E. Kelley, “Critical-path planning and scheduling: Mathematical basis”, Operations Research 9, pp. 296-320, 1961) mainly focus on deterministic systems, more researchers have recently moved to flexible and stochastic systems. In Nam's work (I. hyun Nam, “Dynamic scheduling for a flexible processing network”, Operations Research 49, pp. 305-315, 2001), the scheduling policies for flexible systems were investigated. This work analyzed an open processing network model with discretionary routing and showed, in general, that unbalanced workload routing with priority sequencing gives better performance than a balanced one. Chou et al. (M. C. Chou, H. Liu, M. Queyranne and D. Simchi-Levi, “On the asymptotic optimality of a simple on-line algorithm for the stochastic single-machine weighted completion time problem and its extensions”, Operations Research 54, pp. 464-474, 2006) studied a stochastic single machine problem, where the actual processing time of tasks are not known until processing is complete. They proved that when task weights and processing times are bounded and task processing times are mutually independent random variables, a weighted shortest expected processing time among available jobs (WSEPTA) heuristic is asymptotically optimal for the single-machine problem. Cres et al. (H. Cres and H. Moulin, “Scheduling with opting out: Improving upon random priority”, Operations Research 49, pp. 565-577, 2001) studied the problem where agents can opt out. They showed that the familiar random priority (RP) mechanism can be improved upon by another mechanism dubbed probabilistic serial (PS). Gilland et al. (W. G. Gilland, “Effective sequencing rules for closed manufacturing networks”, Operations Research 49, pp. 759-770, 2001) developed a method for determining sequencing policies to effectively control a multi-station closed queuing network. Here, a Brownian control problem that approximates the original queuing network is formulated and used to develop a dynamic sequencing policy that seeks to prevent idleness, unless the system is at a face of a workload imbalance polytope that arises in the Brownian formulation.
Although the aforementioned scheduling problems have been successfully applied to various industrial areas, they have limitations in CAD scheduling, due to the unique characteristics of whole-body CAD summarized as follows.
First, the schedule of whole-body CAD is highly flexible. The accuracy and speed of CAD systems, however, is significantly different with different schedules. Second, due to missing data, artifacts or diseases, the scheduler of whole-body CAD must be an active one. In other words, the scheduling must be adaptive to the specific patient data at the runtime. Refer to the previous example, in general cases, the detector of iliac bifurcation should be fired next to the “femoral head localization”. However, for a patient who has an artificial mental femoral head, the femoral head detector might not detect it correctly and usually return a result with very low confidence. In this situation, instead of firing the “iliac bifurcation detector”, the scheduler should trigger the detectors of other organs, e.g., kidneys, which can be localized accurately without the inference of femoral heads. Third, multiple tasks are often statistically dependent. Refer to the previous example, “iliac bifurcation localization” is statistically dependent on “femoral heads localization”, as the relative locations of the iliac bifurcation with respect to the femoral heads are not deterministic. Finally, the outcome of tasks usually embeds uncertainties. Since tasks are mutually dependent, uncertainties in one task might influence the speed and accuracy of other tasks.
Accordingly, there exists a need for scheduling tasks in whole-body CAD at high speeds and with great accuracy.